package EnterpriseAlgorithm.Stack_Queue.Code.ReverseStackRecursion;

import java.util.Stack;

class Solution {
    public void reverseStack(Stack<Integer> stack) {
        if (stack.isEmpty()) { // 1. 判断 --> 结束条件
            return;
        }
        int i = getAndRemoveLastElement(stack);  //2. 取栈底
        reverseStack(stack);  //3.递归取栈底
        stack.push(i);  //4. 恢复栈
    }

    private int getAndRemoveLastElement(Stack<Integer> stack) {
        int result = stack.pop(); //1. 先保存取出的当前栈顶元素
        if (stack.isEmpty()) {  //2. 判空 --> 递归结束的条件
            return result;
        } else {
            int last = getAndRemoveLastElement(stack);  // 3. 递归--> 从 1 重复执行
            stack.push(result); // 4. 恢复原栈
            return last;  // 5. 返回结果
        }
    }
    /*
    除了栈底元素作为result返回外，其他递归的都会在 pop后再 push
    而栈底元素result返回被List接收，一直递归到结束。
     */
}